package com.hqq.sort.insert;

import com.hqq.sort.Sort;

/**
 * ShellSort
 * 希尔排序 [最小增量排序]
 * 原理:
 * 使得数组中任意间隔为h的元素都是有序的
 * 适用场景:
 * 解决排序又没有系统排序函数可用[直接接触硬件或者嵌入式系统]
 * Created by heqianqian on 2017/8/3.
 */
public class ShellSort extends Sort {

    public static void sort(Comparable[] a) {
        int length = a.length;
        int h = 1;
        while (h < length / 3) {
            h = 3 * h + 1;//设置增量
        }
        while (h >= 1) {
            for (int i = h; i < length; i++) {
                //将a[i]插入到a[i-h],a[i-2*h],a[i-3*h]...之中
                for (int j = i; j >= h && (less(a[j], a[j - h])); j--) {
                    exchange(a, j, j - h);
                }
            }
            h = h / 3;
        }
    }

}
